\documentclass[11pt,letter]{article}
\usepackage[top=1in, bottom=1in, left=1in, right=1in]{geometry}
\usepackage{setspace}
\usepackage{subfigure}
\usepackage{listings}
\usepackage{amsmath, amsthm, amssymb, amsfonts}
\usepackage[pdftex]{graphicx}
\begin{document}
\doublespacing
\title{Graph-based Multi-relational Modeling Language (GMRML) Manual}
\author{Version 1.0}
\date{}
\maketitle
\begin{center}
\tableofcontents
\end{center}
\pagebreak
\section{Introduction}
This  document  describes  the Graph-based  Multi-Relational  Modeling
Language  (GMRML) which is  an XML  based format  for the  exchange of
graph-based multi-relational data. The goal of GMRML is to serve as an
open  and  well-documented  format  for  the exchange  of  data  among
Graph-based Data Mining researchers.  GMRML differs form GraphML, GLX,
GML, XGMML  and SVG  as it is  specifically designed  for representing
multi-relational data modeled as graphs (See Section \ref{usage} for a
more detailed discussion of the differences).
\section{Basic Concepts}
Figure  \ref{overview} illustrates  the  basic concepts  of GMRML.   A
GMRML file  basically encodes one or  more graphs each of  which has a
unique identifier and  may be associated with a  number of properties.
Every property, has  a name, the type of the  data associated with the
property, which  may be an integer,  float, boolean or  string and the
value  of this  property.  Each  such graph  consists of  a  number of
vertices each of  which has a unique identifier and  a number of edges
(also  with a  unique identifier)  between  any two  vertices in  the
graph.   The vertices  and edges  can be  associated  with properties.
Here  again,  every  property,  has  a  name, the  type  of  the  data
associated with the property, which  may be an integer, float, boolean
or string and the value of  this property.  The edges can be directed
or undirected and self-loops and multi-edges are allowed.
\begin{figure}
\centering
\includegraphics[scale =0.45]{overview}
\caption{An Overview of Basic Concepts in GMRML}
\label{overview}
\end{figure}
\section{Description of Tags}
Each of the  concepts introduced in the previous  section has either a
tag or an attribute associated  with them. Figure \ref{tags} shows how
each concept translates to a tag or an attribute.
\begin{figure}
\centering
\includegraphics[scale =0.45]{tags}
\caption{An Overview of Tags and Attributes in GMRML}
\label{tags}
\end{figure}
\subsection{Header}
Every valid GMRML file has a header as shown below.\\
\makebox[\textwidth]{\hrulefill}
\begin{verbatim}
<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE GMRML SYSTEM "gmrml.dtd">
\end{verbatim}
\makebox[\textwidth]{\hrulefill}
\subsection{GMRML}
The entire document is enclosed in the GMRML tag as shown below. 
\\
\makebox[\textwidth]{\hrulefill}
\begin{verbatim}
<GMRML>
 ...
</GMRML>
\end{verbatim}
\makebox[\textwidth]{\hrulefill}
\subsection{GRAPH}
Within the GMRML tags there are  one or more graph, each enclosed in a
GRAPH  tag  as shown  below.   Every  graph  has a  unique  identifier
specified  by  the  ID  attribute.  Enclosed in  GRAPH  tags  are  the
vertices, edges and properties of  the graph each of which is enclosed
in VERTEX, EDGE and PROPERTY  tags respectively.  VERTEX and EDGE tags
may  themselves  enclose one  or  more  PROPERTY  tags. Note  that,  a
PROPERTY tag  enclosed in the GRAPH  tag (a sibling of  the VERTEX and
EDGE tags  in the GRAPH)  encodes a property  of the graph as  a whole
while a  PROPERTY tag  enclosed in  the VERTEX or  EDGE tag  encodes a
property of the specific vertex or edge.
\\
\makebox[\textwidth]{\hrulefill}
\begin{verbatim}
<GRAPH ID="1">
 ...
</GRAPH>
\end{verbatim}
\makebox[\textwidth]{\hrulefill}
\subsection{PROPERTY}
The  PROPERTY tag  has three  attributes, NAME,  TYPE and  VALUE which
encode  the  name, the  data  type  which  must be  either  ``integer,
``float,",``boolean" or ``string" and the actual value of the property
respectively.
\\
\makebox[\textwidth]{\hrulefill}
\begin{verbatim}
<PROPERTY NAME="age" TYPE="integer" VALUE="5"\>
\end{verbatim}
\makebox[\textwidth]{\hrulefill}
\begin{verbatim}
<PROPERTY NAME="name" TYPE="string" VALUE="fluffy"\>
\end{verbatim}
\makebox[\textwidth]{\hrulefill}
\begin{verbatim}
<PROPERTY NAME="gpa" TYPE="float" VALUE="3.8"\>
\end{verbatim}
\makebox[\textwidth]{\hrulefill}
\begin{verbatim}
<PROPERTY NAME="flag" TYPE="boolean" VALUE="true"\>
\end{verbatim}
\makebox[\textwidth]{\hrulefill}
\subsection{VERTEX }
The VERTEX tag has a  single unique attribute called ID which uniquely
identifies the vertex in the graph as shown below.
\\
\makebox[\textwidth]{\hrulefill}
\begin{verbatim}
<VERTEX ID= "1">
  ...
 </VERTEX>
\end{verbatim}
\makebox[\textwidth]{\hrulefill}
\subsection{EDGE}
The EDGE  tag has four  attributes ID, DIRECTED, VERTEX1  and VERTEX2
which uniquely identifies the edge,  indicates if the edge is directed
and specifies the vertices between which the edge is present. Not that
the  attributes VERTEX1  and  VERTEX2  specify an  order  and hence  a
direction if the DIRECTED attribute is ``true".
\\
\makebox[\textwidth]{\hrulefill}
\begin{verbatim}
<EDGE ID = "1" DIRECTED="true" VERTEX1="1" VERTEX2="2"> 
  ...
</EDGE>
\end{verbatim}
\makebox[\textwidth]{\hrulefill}
\begin{verbatim}
<EDGE ID= "1" DIRECTED="false" VERTEX1="1" VERTEX2="2"> 
  ...
</EDGE>
\end{verbatim}
\makebox[\textwidth]{\hrulefill}
\section{Representing Data with GMRML}
We  now  present  a  few  examples  that  illustrate  how  graph-based
multi-relational data can be encoded using GMRML.
\subsection{Social Network}
Our  first   example  is   a  social  network   as  shown   in  Figure
\ref{social_network}. A typical social network is a simple graph where
the vertices  represent individuals and  the edges represent  a single
social   relations.  Examples   of   such  data   can   be  found   at
http://vlado.fmf.uni-lj.si/pub/networks/pajek/.  Such a social network
can be represented in the GMRML format by representing each individual
as a  VERTEX and every  social relation as  an EDGE.  As there  are no
data  associated with the  individuals and  relations, there  would be
PROPERTY tags. This is illustrated below.
\begin{figure}
\centering
\includegraphics[scale =0.45]{social_network}
\caption{A Social Network}
\label{social_network}
\end{figure}
\\
\makebox[\textwidth]{\hrulefill}
\begin{verbatim}
<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE GMRML SYSTEM "gmrml.dtd">
<GMRML>
    <GRAPH ID= "1">
        <VERTEX ID= "1"> </VERTEX>
        <VERTEX ID= "2"> </VERTEX>
        ...
        <EDGE ID= "1" DIRECTED="false" VERTEX1="1" VERTEX2="2"> </EDGE>
        <EDGE ID= "2" DIRECTED="false" VERTEX1="2" VERTEX2="3"> </EDGE>
        ...
    </GRAPH>
</GMRML>
\end{verbatim}
\makebox[\textwidth]{\hrulefill}
\subsection{Gene Interaction Network}
Our  next example is  a gene  interaction network  as shown  in Figure
\ref{gene_interaction_network}. A typical  gene interaction network is
basically a  graph where  the vertices represent  genes and  the edges
represent  interactions.  Examples  of  such  data  can  be  found  at
http://www.kegg.org.  Generally  in a gene  interaction network, every
gene is associated  with a name, a function  and a localization. Every
interaction is associated with a  weight. There may also be additional
data associated with the genes  and interactions but for simplicity we
only consider the interaction weight, the gene name, gene function and
gene localization. Clearly, additional data can be represented in a
similar way. 
\begin{figure}
\centering
\includegraphics[scale =0.45]{gene_interaction_network}
\caption{A Gene Interaction Network}
\label{gene_interaction_network}
\end{figure}
\\
\makebox[\textwidth]{\hrulefill}
\begin{verbatim}
<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE GMRML SYSTEM "gmrml.dtd">
<GMRML>
    <GRAPH ID= "1">
        <VERTEX ID= "1"> 
            <PROPERTY NAME="function" TYPE="string" VALUE="cell_division"\>
            <PROPERTY NAME="localization" TYPE="string" VALUE="nucleus"\>
        </VERTEX>
        <VERTEX ID= "2"> 
            <PROPERTY NAME="function" TYPE="string" VALUE="cell_division"\>
            <PROPERTY NAME="localization" TYPE="string" VALUE="nucleus"\>
        </VERTEX>
        ...
        <EDGE ID= "1" DIRECTED="false" VERTEX1="1" VERTEX2="2"> 
            <PROPERTY NAME="interaction-weight" TYPE="float" VALUE="0.5"\>
        </EDGE>
        ...
    </GRAPH>
</GMRML>
\end{verbatim}
\makebox[\textwidth]{\hrulefill} Such  a gene interaction  network can
be represented  in the  GMRML format by  representing each gene  as an
VERTEX and  every interaction as an EDGE.   Additional data associated
with the genes and interactions  can be represented using the PROPERTY
tags.
\subsection{World Wide Web}
Our last example is a graph  representing a part of the World Wide Web
shown in Figure \ref{www}. Typical data of this genre would consist of
webpages  and  links. The  significant  difference  from the  previous
examples is that the links  are directed. There may also be additional
data associated  with the pages and  links but for  simplicity we only
consider the webpages and  the links between them. Clearly, additional
data  can  be  represented  as  shown in  the  previous  example.   To
represent such  data, every webpage  is represented with a  VERTEX tag
and  every  link  is represented  by  a  EDGE  tag. To  represent  the
direction of  the link  we use the  DIRECTED attribute. This  is shown
below.  Using this  scheme, a graph with both  directed and undirected
edges can  be easily  represented by specifying  the value  ``true" or
``false" for the DIRECTED attribute.
\begin{figure}
\centering
\includegraphics[scale =0.45]{web}
\caption{Data Extracted from WWW}
\label{www}
\end{figure}
\\
\makebox[\textwidth]{\hrulefill}
\begin{verbatim}
<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE GMRML SYSTEM "gmrml.dtd">
<GMRML>
    <GRAPH ID = "1">
        <VERTEX ID= "1"> </VERTEX>
        <VERTEX ID= "2"> </VERTEX>
        ...
        <EDGE ID= "1" DIRECTED="true" VERTEX1="1" VERTEX2="2"> 
        </EDGE>
        ...
    </GRAPH>
</GMRML>
\end{verbatim}
\makebox[\textwidth]{\hrulefill}
\section{Purpose of GMRML\label{usage}}
A variety  of XML based formats  such as GraphML, GLX,  GML, XGMML and
SVG  have been  developed for  graph  data. GMRML  differs from  these
formats in the following aspects.
\begin{enumerate}
\item GMRML  has been designed for  representing multi-relational data
  represented as graphs.
\item GMRML is a significantly smaller specification.
\item GMRML is specifically targeted for exchanging data sets commonly
  used for benchmarking graph-based data mining algorithms.

\end{enumerate}
The key  advantages of  using GMRML over  other XML formats  for graph
data include the following.
\begin{enumerate}
\item  Availability of specific  constructs required  for representing
  multi-relational data as graphs.
\begin{enumerate}
\item Support for directed, undirected and mixed edges.
\item Support for self loops and multi-edges.
\item Support for associating  arbitrary data with vertices, edges and
  entire graphs.
\item Support  for indicating  data types (integers,  floats, booleans
  and strings).
\end{enumerate}
\item  Small  and  simple  to  understand.  Hence  encoding  data  and
  extracting required data becomes easier.
\item  As  most  other  formats  are  not  specifically  targeted  for
  graph-based multi-relational data, there are more than one seemingly
  natural ways to  encode data, using a variety  of constructs defined
  in the format. Often in the case of GMRML, there is a single obvious
  way  to  encode  data.  This  makes  the  process  of  encoding  and
  extracting data easier.
\end{enumerate}
\section{Limitations and Future Work}
The present  version of GMRML  does not support nested  graphs (graphs
were the  vertices and edges  can themselves be associated  with other
graphs)  and hyper  graphs (graphs  with edges  between more  than two
vertices). As  a part of  our future work  we plan to extend  GMRML to
support them.
\end{document} 

